package com.llk.algorithm;

import java.util.Arrays;

/**
 * 高度检查器
 *
 * <p>
 * 学校打算为全体学生拍一张年度纪念照。根据要求，学生需要按照 非递减 的高度顺序排成一行。
 * 排序后的高度情况用整数数组 expected 表示，其中 expected[i] 是预计排在这一行中第 i 位的学生的高度（下标从 0 开始）。
 * 给你一个整数数组 heights ，表示 当前学生站位 的高度情况。heights[i] 是这一行中第 i 位学生的高度（下标从 0 开始）。
 * 返回满足 heights[i] != expected[i] 的 下标数量 。
 * <p>
 *
 * 思路：
 * 先将入参数组赋值并从大到小排序，后将排序后的数组与原数组相同位置的元素比较大小。
 *
 * @author liulukuan
 * @date 2022/6/13 11:41
 **/
public class HeightChecker {

    public static void main(String[] args) {
        System.out.println(heightChecker2(new int[]{6, 1, 2, 3, 4, 5}));
    }

    public static int heightChecker(int[] heights) {
        int[] arr = Arrays.copyOf(heights, heights.length);
        Arrays.sort(arr);

        int count = 0;
        for (int i = 0; i < arr.length; i++) {
            if (heights[i] != arr[i]) {
                count++;
            }
        }

        return count;
    }

    public static int heightChecker2(int[] heights) {
        int[] arr = new int[101];
        for (int height : heights) {
            arr[height]++;
        }
        int count = 0;
        for (int i = 1, j = 0; i < arr.length; i++) {
            while (arr[i]-- > 0) {
                if (heights[j++] != i) {
                    count++;
                }
            }
        }
        return count;
    }
}
